//
//  LCFive.swift
//  LeetCode
//
//  Created by migu on 2021/7/15.
//  Copyright © 2021 LBB. All rights reserved.
//
//给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。
//
//已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。
//
//每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。
//请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？
//输入：k = 1, n = 2
//输出：2
//解释：
//鸡蛋从 1 楼掉落。如果它碎了，肯定能得出 f = 0 。
//否则，鸡蛋从 2 楼掉落。如果它碎了，肯定能得出 f = 1 。
//如果它没碎，那么肯定能得出 f = 2 。
//因此，在最坏的情况下我们需要移动 2 次以确定 f 是多少。


import Foundation
class LCFive {
    func superEggDrop(_ k: Int, _ n: Int) -> Int {
        return dpEgg(k, n, n)
        
//        var egg:Int = 0
//        var floor:Int = n
//        var times:Int = 0
//        //最多二分次数k-1次
//        while floor > 1 && times < k - 1{
//            floor = floor/2
//            egg += 1
//            times += 1
//        }
//        //下面还没有遍历的楼层
//        var belowFloor:Int = 0
//        //上面还没有遍历的楼层
//        let onFloor:Int = floor
//        if n>2 && n%2 == 0 && k > 1 {
//            //例如k=2，n=6，二分是3，当前已经对3判断了，所以不需要在对二层判断，需要加上1，2层判断即可
//            floor -= 1
//        }
//        belowFloor = floor
//        return egg + (onFloor > belowFloor ? onFloor : belowFloor)
    }
    
    func dpEgg(_ k: Int, _ n: Int, _ floor: Int) -> Int {
        if k == 1 {
            return n
        }
        if n == 0 {
            return 0
        }
        if n < 2 {
            return 1
        }
        var floor1:Int = n
        var floor2:Int = n - floor1
        var min1:Int = -1
        var min2:Int = -1
        while floor1 > 0 {
            let belowFloor:Int = dpEgg(k-1,floor1, floor1)
            let onFloor:Int = dpEgg(k,floor2, floor2)
            floor1 -= 1
            floor2 = n - floor1
            if min1 < 0  {
                min1 = belowFloor
            }
            if belowFloor < min1 {
                min1 = belowFloor
            }
            if min2 < 0  {
                min2 = onFloor
            }
            if onFloor < min2 {
                min2 = onFloor
            }
        }
        
        return min1 > min2 ? min1 : min2 + 1
    }
}
